package com.zk;

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * ARC (Optimal Alphabetic Radix-Code Tree Problem)
 * http://www.blogjava.net/changedi/archive/2014/04/16/412531.html
 */
public class ARCProblem implements AlgoInteraction {

    public double minmumWeight(double[] weightArray) {
        Arrays.sort(weightArray);
        return f(weightArray, 0, weightArray.length - 1);
    }

    private double f(double[] weightArray, int firstIndex, int lastIndex) {
        if (firstIndex == lastIndex) {
            return .0D;
        }

        double min = Double.MAX_VALUE;
        for (int d = firstIndex; d < lastIndex; d++) {
            double t = f(weightArray, firstIndex, d) + f(weightArray, d + 1, lastIndex) + sum(weightArray, firstIndex, lastIndex);
            if (t < min) {
                min = t;
            }
        }

        return min;
    }

    private double sum(double[] weightArray, int p, int q) {
        double result = .0D;
        for (int i=p; i <= q; i++) {
            result += weightArray[i];
        }
        return result;
    }

    @Override
    public void exec(Scanner scanner, PrintWriter printWriter) {
        printWriter.println("请输入权重(支持小数),每行一个(-1 表示结束输入):");

        List<Double> weightList = new ArrayList<>(8);
        double curInt = -1D;
        while ((curInt = scanner.nextDouble()) != -1) {
            weightList.add(curInt);
        }

        printWriter.println("您输入的权重数组为:" + weightList);

        double[] weightArray = weightList.stream().mapToDouble(Double::doubleValue).toArray();
        double weight = minmumWeight(weightArray);

        printWriter.println("成本最小权重为:" + weight);
    }

}
